package chapter3.two;

import chapter3.BiNode;

public class Test {

	/**
	 * 把有序数组转换为二叉树
	 * @param arr
	 * @param start
	 * @param end
	 * @return
	 */
	public static BiNode arraytotree(int[] arr,int start,int end) {
		BiNode root=null;
		
		if(end>=start) {
			root=new BiNode();
			
			int mid=(start+end+1)/2;
			
			//树的根节点为数组中间的元素
			root.data=arr[mid];
			
			//递归的用左半部分数组构造root的左子树
			root.lChild=arraytotree(arr,start,mid-1);
			
			//递归的用右半部分数组构造root的右子树
			root.rChild=arraytotree(arr,mid+1,end);
			
			
		}else {
			root=null;
		}
		
		return root;
		
		
	}
	
	/**
	 * 用中序遍历的方式打印出二叉树节点的内容
	 * @param root
	 */
	public static void printTreeMidOrder(BiNode root) {
		if(root==null) {
			return;
		}
		
		//遍历root节点的左子树
		if(root.lChild!=null) {
			printTreeMidOrder(root.lChild);
		}
		
		//遍历root节点
		System.out.print(root.data+" ");
		
		//遍历root节点的右子树
		if(root.rChild!=null) {
			printTreeMidOrder(root.rChild);
		}
		
	}
	
	public static void main(String[] args) {
		int arr[]= {1,2,3,4,5,6,7,8,9};
		
		System.out.print("数组：");
		
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}
		
		System.out.println();
		
		BiNode root;
		
		root=arraytotree(arr,0,arr.length-1);
		
		System.out.print("转换成树的中序遍历为：");
		
		printTreeMidOrder(root);
		
		//System.out.println();
	}
}
